本文最后编辑于 前，其中的内容可能需要更新。
题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
1
2
| 输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
|
示例 2：
1
2
| 输入：l1 = [], l2 = []
输出：[]
|
示例 3：
1
2
| 输入：l1 = [], l2 = [0]
输出：[0]
|
提示：
- 两个链表的节点数目范围是
[0, 50]
-100 <= Node.val <= 100l1 和 l2 均按 非递减顺序 排列
链接：
https://leetcode-cn.com/problems/merge-two-sorted-lists
题目分析
合并两个升序链表，只需要用两个指针分别遍历两个链表，每次将值小的那个结点添加到合并链表中即可。如果一个链表为空，则直接返回另一个链表（当两个都为空时返回的也是空）。当迭代到某一个链表为空之后，只需将另外一个链表剩下的部分接到最后即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr) return l2;
if(l2 == nullptr) return l1;
ListNode *head, *tail;
if(l1->val <= l2->val){
head = l1;
l1 = l1->next;
}
else{
head = l2;
l2 = l2->next;
}
tail = head;
while(l1 != nullptr && l2 != nullptr){
if(l1->val <= l2->val){
tail->next = l1;
l1 = l1->next;
}
else{
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1?l1:l2;
return head;
}
};
|
时间复杂度：$O(m+n)$，其中 $m、n$ 分别为两个链表的大小。因为我们最多只对两个链表进行了一次遍历便可以完成合并的操作。
空间复杂度：$O(1)$。只需要常数个指针进行遍历即可。
官方题解
思路与上面相同，但是我们可以使用一个哨兵结点 prehead 作为开头，这样就可以不用额外判断合并后的链表是以哪个链表作为头结点，从而代码可以合并到后面迭代的循环中，更为简洁。这里的 prev 相当于上面的 tail。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* preHead = new ListNode(-1);
ListNode* prev = preHead;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
prev->next = l1 == nullptr ? l2 : l1;
return preHead->next;
}
};
|